/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: xwl
 * Date: 2023-05-22
 * Time: 21:31
 */

class TreeNode4 {
    int val;
    TreeNode4 left;
    TreeNode4 right;
    TreeNode4() {}
    TreeNode4(int val) { this.val = val; }
    TreeNode4(int val, TreeNode4 left, TreeNode4 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test4 {

    class Solution {

        public TreeNode4 buildTree(int[] inorder, int[] postorder) {
            i = postorder.length - 1;
            return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
        }

        // 用来遍历书的前序遍历数组
        private int i = 0;

        /**
         *
         * @param postorder:树的前序遍历
         * @param inorder:树的中序遍历
         * @param inbegin:查找根节点的始位置
         * @param inend:查找根节点的末位置
         * @return
         */
        public TreeNode4 buildTreeChild(int[] postorder, int[] inorder,int inbegin, int inend) {
            if (inbegin > inend) {
                return null;
            }
            //
            TreeNode4 root = new TreeNode4(postorder[i]);
            //
            int rootIndex = findIndex(inorder, inbegin, inend, postorder[i]);
            i--;
            root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);
            root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex - 1);
            return root;
        }

        /**
         * 查找根节点在中序遍历中的位置
         * @param inorder:中序遍历数组
         * @param inbegin:查找根节点的起始位置
         * @param inend:查找根节点的末位置
         * @param key:待查找的值
         * @return
         */
        public int findIndex(int[] inorder,int inbegin, int inend, int key) {
            for (int i = inbegin; i <= inend; i++) {
                if (inorder[i] == key) {
                    return i;
                }
            }
            return 0;
        }
    }
}
